package org.apache.commons.graph.algorithms.flow

import org.apache.commons.graph.CommonsGraph.findMaxFlow
import org.apache.commons.graph.CommonsGraph.newDirectedMutableGraph
import org.apache.commons.graph.builder.AbstractGraphConnection
import org.apache.commons.graph.model.BaseLabeledVertex
import org.apache.commons.graph.model.BaseLabeledWeightedEdge
import org.apache.commons.graph.model.BaseWeightedEdge
import org.apache.commons.graph.model.DirectedMutableGraph
import org.apache.commons.graph.weight.primitive.IntegerWeightBaseOperations
import org.junit.Assert
import org.junit.Test

/*
* Licensed to the Apache Software Foundation (ASF) under one
* or more contributor license agreements.  See the NOTICE file
* distributed with this work for additional information
* regarding copyright ownership.  The ASF licenses this file
* to you under the Apache License, Version 2.0 (the
* "License"); you may not use this file except in compliance
* with the License.  You may obtain a copy of the License at
*
*   http://www.apache.org/licenses/LICENSE-2.0
*
* Unless required by applicable law or agreed to in writing,
* software distributed under the License is distributed on an
* "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY
* KIND, either express or implied.  See the License for the
* specific language governing permissions and limitations
* under the License.
*/

/**
 * Test for Ford-Fulkerson algorithm implementation.
 * The test graph is available on
 * [Wikipedia](http://en.wikipedia.org/wiki/Ford%E2%80%93Fulkerson_algorithm#Integral_example).
 */
class FordFulkersonTestCase {
    @Test
    fun testFindMaxFlowAndVerify() {
        val a = BaseLabeledVertex("A")
        val d = BaseLabeledVertex("D")

        val graph: DirectedMutableGraph<BaseLabeledVertex, BaseLabeledWeightedEdge<Int>> =
            newDirectedMutableGraph(object :
                AbstractGraphConnection<BaseLabeledVertex, BaseLabeledWeightedEdge<Int>>() {
                override fun connect() {
                    addVertex(a)
                    val b = addVertex(BaseLabeledVertex("B"))
                    val c = addVertex(BaseLabeledVertex("C"))
                    addVertex(d)

                    addEdge(BaseLabeledWeightedEdge<Int>("A -> B", 1000)).from(a).to(b)
                    addEdge(BaseLabeledWeightedEdge<Int>("A -> C", 1000)).from(a).to(c)
                    addEdge(BaseLabeledWeightedEdge<Int>("B -> C", 1)).from(b).to(c)
                    addEdge(BaseLabeledWeightedEdge<Int>("B -> D", 1000)).from(b).to(d)
                    addEdge(BaseLabeledWeightedEdge<Int>("C -> D", 1000)).from(c).to(d)
                }
            })

        // expected max flow
        val expected = 2000

        // actual max flow
        val actual = findMaxFlow(graph)
            .whereEdgesHaveWeights(BaseWeightedEdge<Int>())
            .from(a)
            .to(d)
            .applyingFordFulkerson(IntegerWeightBaseOperations)

        Assert.assertEquals(expected, actual)
    }

    @Test
    fun testNotConnected() {
        val a = BaseLabeledVertex("A")
        val d = BaseLabeledVertex("D")

        val graph: DirectedMutableGraph<BaseLabeledVertex, BaseLabeledWeightedEdge<Int>> =
            newDirectedMutableGraph(object :
                AbstractGraphConnection<BaseLabeledVertex, BaseLabeledWeightedEdge<Int>>() {
                override fun connect() {
                    addVertex(a)
                    addVertex(BaseLabeledVertex("B"))
                    addVertex(BaseLabeledVertex("C"))
                    addVertex(d)
                }
            })

        // expected max flow
        val expected = 0

        // actual max flow
        val actual = findMaxFlow(graph)
            .whereEdgesHaveWeights(BaseWeightedEdge<Int>())
            .from(a)
            .to(d)
            .applyingFordFulkerson(IntegerWeightBaseOperations)

        Assert.assertEquals(actual, expected)
    }

    @Test
    fun testNotConnected_2() {
        val a = BaseLabeledVertex("A")
        val d = BaseLabeledVertex("D")

        val graph: DirectedMutableGraph<BaseLabeledVertex, BaseLabeledWeightedEdge<Int>> =
            newDirectedMutableGraph(object :
                AbstractGraphConnection<BaseLabeledVertex, BaseLabeledWeightedEdge<Int>>() {
                override fun connect() {
                    addVertex(a)
                    val b = addVertex(BaseLabeledVertex("B"))
                    addVertex(BaseLabeledVertex("C"))
                    addVertex(d)
                    addEdge(BaseLabeledWeightedEdge<Int>("A -> B", 1000)).from(a).to(b)
                }
            })

        // expected max flow
        val expected = 0

        // actual max flow
        val actual = findMaxFlow(graph)
            .whereEdgesHaveWeights(BaseWeightedEdge<Int>())
            .from(a)
            .to(d)
            .applyingFordFulkerson(IntegerWeightBaseOperations)

        Assert.assertEquals(actual, expected)
    }

//    @Test(expected = NullPointerException::class)
//    fun testNullGraph() {
//        val a = BaseLabeledVertex("A")
//        val d = BaseLabeledVertex("D")
//
//        findMaxFlow(null as DirectedMutableGraph<BaseLabeledVertex?, BaseLabeledWeightedEdge<Int?>?>?)
//            .whereEdgesHaveWeights(BaseWeightedEdge<Int>())
//            .from(a)
//            .to(d)
//            .applyingFordFulkerson(IntegerWeightBaseOperations)
//    }
//
//    @Test(expected = NullPointerException::class)
//    fun testNullGraphAndVertices() {
//        findMaxFlow(null as DirectedMutableGraph<BaseLabeledVertex?, BaseLabeledWeightedEdge<Int?>?>?)
//            .whereEdgesHaveWeights(BaseWeightedEdge<Int>())
//            .from(null)
//            .to(null)
//            .applyingFordFulkerson(IntegerWeightBaseOperations)
//    }
//
//    @Test(expected = NullPointerException::class)
//    fun testNullVertices() {
//        val graph =
//            DirectedMutableGraph<BaseLabeledVertex, BaseLabeledWeightedEdge<Int>>()
//
//        // actual max flow
//        findMaxFlow(graph)
//            .whereEdgesHaveWeights(BaseWeightedEdge<Int>())
//            .from(null)
//            .to(null)
//            .applyingFordFulkerson(IntegerWeightBaseOperations)
//    }
}
